/**
 * 
 * 二叉搜索树与双向链表
 * 
 * 描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示


数据范围：输入二叉树的节点数 
0
≤
n
≤
1000
0≤n≤1000，二叉树中每个节点的值 
0
≤
v
a
l
≤
1000
0≤val≤1000
要求：空间复杂度
O
(
1
)
O(1)（即在原树上操作），时间复杂度 
O
(
n
)
O(n)

注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
输入描述：

二叉树的根节点
返回值描述：

双向链表的其中一个头节点。

 * 
 */
public class 二叉搜索树与双向链表 {
    
    public static void main(String[] args) {
        
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(2);
        root.left.left.left.left = new TreeNode(1);

        TreeNode result = Convert(root);

        System.out.println(result.toString());
    }

    public static TreeNode Convert(TreeNode pRootOfTree) {

        inorder(pRootOfTree);
        return head;
    }

    private static TreeNode prev = null;
    private static TreeNode head = null;

    private static void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        if (prev == null) {
            head = node;
        } else {
            prev.right = node;
            node.left = prev;
        }
        prev = node;
        inorder(node.right);
    }
}
